package dynamicArray;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/9
 * 动态数组
 *
 * 缓存与局部性原理:
 * 计算过程:CPU先读取内存中的数据，之后将结果再写入到内存中；CPU的运行效率要远远高于内存
 * 在内存和CPU之间提供了缓存，作用:提高CPU读写数据的效率，每次会缓存64个字节(缓存行，缓存的最小单位，cache-line)
 * 按行读取能够提高缓存命中率，因此遍历二维数组一般将行遍历作为外循环
 */
public class DynamicArray implements Iterable<Integer>{

    // 逻辑大小，动态数组中有效元素的个数
    private int size = 0;

    // 数组初始容量，ArrayList为10
    private int capacity = 8;

    // 数组
    private int[] array = {};

    /**
     * 向数组中最后的位置插入元素
     * @param element 待插入的元素
     */
    public void addLast(int element) {
        checkAndGrow();
        array[size] = element;
        size++;
    }

    /**
     * 向数组中指定位置插入元素
     * @param index 索引
     * @param element 待插入元素
     * 过程分析：将要插入的索引之后的元素均向后移动一位；将待插入的元素赋值给目标索引位置；size往后移动一位
     */
    public void add(int index, int element) {
        // 容量初始化和检查是否需要扩容
        checkAndGrow();
        if (index >= 0 && index < size) {
            // 1.数组拷贝，将要插入的索引之后的元素均向后移动一位
            /*
            参数说明：源数组，源数组拷贝元素的起始位置，目标数组，目标数组拷贝元素的起始位置，拷贝元素的个数
             */
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        // 如果index = size，相当于在最后插入addLast，此时不需要移动任何元素

        // 2.将待插入的元素赋值给目标索引位置
        array[index] = element;
        // 3.size向后移的一位
        size++;

    }

    /**
     * 根据元素索引获取元素
     * @param index 元素索引
     * @return 元素
     */
    public int getElement(int index) {
        if (index >= 0 && index < size) {
            return array[index];
        }
        throw new IndexOutOfBoundsException();
    }

    /**
     * 遍历数组中的元素
     * @param action 调用方
     */
    public void forEachArray(Consumer<Integer> action) {
        for (int i = 0; i < size; i++) {
            action.accept(array[i]);
        }
    }

    /**
     * 遍历数组中的元素
     * @return 迭代器
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;
            // 判断有没有下一个元素
            @Override
            public boolean hasNext() {
                return i < size;
            }
            // 返回当前元素，并移动到下一位
            @Override
            public Integer next() {
                return array[i++];
            }
        };
    }

    /**
     * 根据索引删除元素并返回
     * @param index 索引
     * @return 元素
     */
    public int remove(int index) {
        int element = array[index];
        if (index < size -1) {
            System.arraycopy(array, index, array, index -1, size - index - 1);
        }
        size--;
        return element;
    }

    /**
     * 扩容检查
     */
    public void checkAndGrow() {
        // 使用时才给赋予初始值，懒加载节约空间
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {
            // 如果有效元素个数达到了容量峰值，进行扩容
            // 容量为之前的1.5倍
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];

            // 数组拷贝
            System.arraycopy(array, 0, newArray, 0, size);

            // 赋值给之前的数组
            array = newArray;
        }
    }
}
